package com.cat.dataStructure03;

import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/
 * @create 2025/11/21 12:35
 * @since JDK17
 */

public class Solution97 {
    static int MAXN = ((int) 1e5) + 1, LIMIT = 34, power, m;
    static int[][] stjump = new int[MAXN][LIMIT];
    static long[][] stsum = new long[MAXN][LIMIT];
    static int[] kbits = new int[LIMIT];
    static void build(long k) {
        power = 0;
        while ((1l << power) <= (k >> 1)) {
            power++;
        }
        m = 0;
        for (int p = power; p >= 0; p--) {
            if ((1l << p & k) != 0) {
                kbits[m++] = p;
                k -= 1l << p;
            }
        }
    }

    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        build(k);
        int n = receiver.size();
        for (int i = 0; i < n; i++) {
            stjump[i][0] = receiver.get(i);
            stsum[i][0] = receiver.get(i);
        }
        for (int p = 1; p <= power; p++) {
            for (int i = 0; i < n; i++) {
                stjump[i][p] = stjump[stjump[i][p - 1]][p - 1];
                stsum[i][p] = stsum[i][p - 1] + stsum[stjump[i][p - 1]][p - 1];
            }
        }
        long sum, ans = 0;
        for (int i = 0, cur; i < n; i++) {
            sum = cur = i;
            for (int j = 0; j < m; j++) {
                sum += stsum[cur][kbits[j]];
                cur = stjump[cur][kbits[j]];
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}
